home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / prlgbnch.lha / queens_8.pl < prev    next >
Text File  |  1990-05-25  |  2KB  |  63 lines
  1. % generated: 10 November 1989
  2. % option(s): 
  3. %
  4. %   (queens) queens_8
  5. %
  6. %   from Sterling and Shapiro, "The Art of Prolog," page 211.
  7. %
  8. %   solve the 8 queens problem
  9.  
  10. queens_8 :- queens(8,_), !.
  11.  
  12. %   This program solves the N queens problem:  place N pieces on an N
  13. %   by N rectangular board so that no two pieces are on the same line
  14. %   - horizontal, vertical, or diagonal.  (N queens so placed on an N
  15. %   by N chessboard are unable to attack each other in a single move
  16. %   under the rules of chess.)  The strategy is incremental generate-
  17. %   and-test.
  18. %
  19. %   A solution is specified by a permutation of the list of numbers 1 to
  20. %   N.  The first element of the list is the row number for the queen in
  21. %   the first column, the second element is the row number for the queen
  22. %   in the second column, et cetera.  This scheme implicitly incorporates
  23. %   the observation that any solution of the problem has exactly one queen
  24. %   in each column.
  25. %
  26. %   The program distinguishes symmetric solutions.  For example, 
  27. %
  28. %   ?- queens(4, Qs).
  29. %
  30. %   produces
  31. %
  32. %   Qs = [3,1,4,2] ;
  33. %
  34. %   Qs = [2,4,1,3]
  35.  
  36. queens(N,Qs) :-
  37.     range(1,N,Ns),
  38.     queens(Ns,[],Qs).
  39.  
  40. queens([],Qs,Qs).
  41. queens(UnplacedQs,SafeQs,Qs) :-
  42.     select(UnplacedQs,UnplacedQs1,Q),
  43.     not_attack(SafeQs,Q),
  44.     queens(UnplacedQs1,[Q|SafeQs],Qs).
  45.  
  46. not_attack(Xs,X) :-
  47.     not_attack(Xs,X,1).
  48.  
  49. not_attack([],_,_) :- !.
  50. not_attack([Y|Ys],X,N) :-
  51.     X =\= Y+N, X =\= Y-N,
  52.     N1 is N+1,
  53.     not_attack(Ys,X,N1).
  54.  
  55. select([X|Xs],Xs,X).
  56. select([Y|Ys],[Y|Zs],X) :- select(Ys,Zs,X).
  57.  
  58. range(N,N,[N]) :- !.
  59. range(M,N,[M|Ns]) :-
  60.     M < N,
  61.     M1 is M+1,
  62.     range(M1,N,Ns).
  63.